/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

/**
 * <p>
 * 反转一个链表的k个节点，仅仅使用常数内存 
 * Given this linked list: 1->2->3->4->5
 * For k = 2, you should return: 2->1->4->3->5
 * For k = 3, you should return: 3->2->1->4->5
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月17日
 */
public class ReverseNodesKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null || k<=1){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //记录分组区间的开始节点
        ListNode pre = dummy;
        ListNode cross = head;
        int count = 0;
        while(cross!=null){
            count++;
            if(count%k ==0){
                //分组区间结束节点
                pre = reverse(pre,cross.next);
                cross = pre.next;
            }else{
                cross = cross.next;
            }
        }
        return dummy.next;
    }

    /**
     * @param pre
     * @param next
     * @return
     * @author towan
     * 2015年6月17日
     */
    private ListNode reverse(ListNode pre, ListNode next) {
        ListNode last = pre.next;
        ListNode cur = last.next;
        while(cur!=next){
            last.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = last.next;
        }
        return last;
    }
}
